/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        //首先计算出整个链表的总长度n，然后使用k = k%n这样就能够知道每一个节点需要移动的位置了
        //然后需要将最后一个节点和第一个节点连接到一起，然后需要找到新链表的头节点,而使用这个公式：
        //新链表的最后一个节点为原链表的第 (n−1)−(k%n) 个节点（从 0 开始计数），这个节点的next就是新链表的头节点
        if(head == nullptr||k == 0)
        {
            return head;
        }
        int n = 1;
        ListNode* cur = head;
        while(cur->next!=nullptr)
        {
            n++;
            cur = cur->next;
        }
        int tmp = (n-1)-(k%n);
        if(tmp == n)
        {
            return head;
        }//链表移动后会回到原来的位置
        //连接头尾
        cur->next = head;
        //找到最后一个链表
        cur = head;
        while(tmp--)
        {
            cur = cur->next;
        }
        //cur指向旋转后新链表的最后一个节点
        ListNode* newhead = cur->next;
        cur->next = nullptr;
        return newhead;
    }
};